package com.congee02;

import java.util.Arrays;

public class FindCircleNum_UnionFind {

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;

        int[] parent = new int[n];

        for (int i = 0 ; i < n ; i ++ ) {
            parent[i] = i;
        }

        for (int from = 0 ; from < n ; from ++ ) {
            for (int to = 0 ; to < n ; to ++ ) {
                if (isConnected[from][to] == 0) {
                    continue;
                }
                union(parent, from, to);
            }
        }

        int ans = 0;
        for (int i = 0 ; i < n ; i ++ ) {
            if (parent[i] == i) {
                ans ++;
            }
        }

        return ans;
    }

    private int root(int[] parent, int cur) {
        return parent[cur] == cur ? cur : (parent[cur] = root(parent, parent[cur]));
    }

    private void union(int[] parent, int x, int y) {
        parent[root(parent, x)] = root(parent, y);
    }


}
